import java.util.HashSet;
import java.util.Set;

public class Test {
    //方法一：二分（最优）
    public int missingNumber(int[] nums){
        int left=0,right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]==mid){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        if(nums[left]== left){
            return left+1;
        }
        return left;
    }

    //方法二：异或
    public int missingNumber1(int[] nums){
        int res=nums.length;
        for(int i=0;i<nums.length;i++){
            res^=i^nums[i];
        }
        return res;
    }

    //方法三：数学（高斯求和）
    public int missingNumber2(int[] nums){
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        return (nums.length*(nums.length+1))/2-sum;
    }

    //方法四：哈希表
    public int missingNumber3(int[] nums){
        Set<Integer> set=new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for(int i=0;i<=nums.length;i++){
            if(!set.contains(i)){
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] nums={0,1,3};
        int[] nums1={0,1,2,3};
        //四种方法测试
        System.out.println(new Test().missingNumber3(nums));
        System.out.println(new Test().missingNumber3(nums1));
    }
}
